package Day16;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * -------------------------------------------------------------------------
 * 题目：
 *      设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 *      如果指定节点没有对应的“下一个”节点，则返回null。
 * -------------------------------------------------------------------------
 * 示例:
 *      输入: root = [2,1,3], p = 1
 *        2
 *       / \
 *      1   3
 *      输出: 2
 * -------------------------------------------------------------------------
 * 方法：
 *      1.中序遍历
 *      2.利用栈
 * -------------------------------------------------------------------------
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public static void main(String[] args) {

    }
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode prev = null, curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev == p) {
                return curr;
            }
            prev = curr;
            curr = curr.right;
        }
        return null;
    }
}
 /*
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode cur = root;
        TreeNode ans = null;
        while (cur != null){
            if (cur.val > p.val){
                ans = cur;
                cur = cur.left;
            }else{
                cur = cur.right;
            }
        }
        return ans;
    }
}
*/